| 翻訳と辞書 |
X-fast trie
In computer science, an x-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time ''O''(log log ''M''), using ''O''(''n'' log ''M'') space, where ''n'' is the number of stored values and ''M'' is the maximum value in the domain. The structure was proposed by Dan Willard in 1982,〔 along with the more complicated y-fast trie, as a way to improve the space usage of van Emde Boas trees, while retaining the ''O''(log log ''M'') query time.
==Structure==
An x-fast trie is a bitwise trie: a binary tree where each subtree stores values whose binary representations start with a common prefix. Each internal node is labeled with the common prefix of the values in its subtree and typically, the left child adds a 0 to the end of the prefix, while the right child adds a 1. The binary representation of an integer between 0 and ''M'' − 1 uses ⌈log2 ''M''⌉ bits, so the height of the trie is ''O''(log ''M'').
All values in the x-fast trie are stored at the leaves. Internal nodes are stored only if they have leaves in their subtree. If an internal node would have no left child, it stores a pointer to the smallest leaf in its right subtree instead, called a ''descendant'' pointer. Likewise, if it would have no right child, it stores a pointer to the largest leaf in its left subtree. Each leaf stores a pointer to its predecessor and successor, thereby forming a doubly linked list. Finally, there is a hash table for each level that contains all the nodes on that level. Together, these hash tables form the level-search structure (LSS). To guarantee the worst-case query times, these hash tables should use dynamic perfect hashing or cuckoo hashing.
The total space usage is ''O''(''n'' log ''M''), since each element has a root-to-leaf path of length ''O''(log ''M'').
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「X-fast trie」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|